package Algorithm.A1;

import java.util.Arrays;
import java.util.Comparator;

/*
* @Author :lcy
* @Description :
 * 算法思路：
 * 按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
 *
 *
 * ，按照对象的权值进行比较，符合条件的对象加入
 * 到链表中，最终按照链表顺序输出最小生成树。
* @Date 2021/11/25 16:39
*/
public class Kruskal {
    public static void main(String[] args) {
        //用类EdgeT创建对象，录入对象信息
        EdgeT[] edges = new EdgeT[10];
        edges[0] = new EdgeT(1, 2, 6);
        edges[1] = new EdgeT(1, 3, 1);
        edges[2] = new EdgeT(1, 4, 5);
        edges[3] = new EdgeT(2, 3, 5);
        edges[4] = new EdgeT(2, 5, 3);
        edges[5] = new EdgeT(3, 4, 5);
        edges[6] = new EdgeT(3, 5, 6);
        edges[7] = new EdgeT(3, 6, 4);
        edges[8] = new EdgeT(4, 6, 2);
        edges[9] = new EdgeT(5, 6, 6);

        kruskal(edges);
    }

    public static void kruskal(EdgeT[] edges) {
        Arrays.sort(edges, Comparator.comparingInt(o -> o.weight));//根据weight对数组进行排序

        // 定义一个一维数组，下标为边的起点，值为边的终点
        int[] temp = new int[edges.length + 1];

        for (EdgeT edge : edges) {
            // 找到起点和终点在临时边数组中的最后连接点
            int start = find(temp, edge.start);
            int end = find(temp, edge.end);

            // 通过起点和终点找到的最后连接点是否为同一个点，是则产生回环
            if (start != end) {
                // 没有产生回环则将临时数组中，起点为下标，终点为值
                temp[start] = end;
                System.out.println(edge.start + "->" + edge.end + "：" + edge.weight);
            }
        }
    }

    public static int find(int temp[], int index) {
        while (temp[index] > 0) {
            index = temp[index];
        }
        return index;
    }
}
// 该类用一个EdgeT类构成一个邻接边的信息，包括邻接边的起始顶点与结束顶点，权值。
class EdgeT {
    int start;
    int end;
    int weight;

    public EdgeT(int start, int end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}
